package priv.sort.quick;

import priv.sort.util.SortUtil;

// 快速排序
public class QuickSort {
    public static void sort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int pivot = partition(arr, left, right);
            // 对基准值左边排序
            quickSort(arr, 0, pivot - 1);
            // 对基准值右边排序
            quickSort(arr, pivot + 1, right);
        }
    }

    private static int partition(int[] arr, int left, int right) {
        // 基准
        int pivot = arr[left];
        int i = left + 1;
        // 当前元素小于基准，交换他们
        for (int j = i; j <= right && arr[j] < pivot; j++) {
            SortUtil.swap(arr, i++, j);
        }
        // 交换基准值元素和小于基准值元素数组的最后一个元素
        SortUtil.swap(arr, left, i - 1);
        return i - 1;
    }
}
